package pers.tz.题目.nowcorder;

import java.util.*;

/**
 * @author irony
 * @date 2024-03-13
 */
public class 字符串的全部不重复的子序列 {
// 描述
//给定一个字符串s，长度为n，求s的所有子序列
//1.子序列: 指一个字符串删掉部分字符（也可以不删）形成的字符串，可以是不连续的，比如"abcde"的子序列可以有"ace","ad"等等
//2.将所有的子序列的结果返回为一个字符串数组
//3.字符串里面可能有重复字符，但是返回的子序列不能有重复的子序列，比如"aab"的子序列只有"","a","aa","aab","ab","b"，不能存在2个相同的"ab"
//4.返回字符串数组里面的顺序可以不唯一

    public static void main(String[] args) {
        System.out.println(Arrays.toString(generatePermutation("dbcq")));
    }

    public static String[] generatePermutation(String s) {
        Set<String> ans = new HashSet<>();
        process(s.toCharArray(), 0, ans, "");
        return ans.toArray(new String[0]);
    }

    private static void process(char[] chars, int index, Set<String> ans, String path) {
        if (index == chars.length) {
            ans.add(path);
            return;
        }

        process(chars, index + 1, ans, path);
        process(chars, index + 1, ans, path + chars[index]);
    }
}
